package com.xsomnus.data_structures.searching;

/**
 * @author @xsomnus666_xiawenye★
 * @since 2019/7/4 0004 11:31
 * - 才需学也,学需静也/非淡泊无以明志，非宁静无以致远
 * <desc>
 *     二分搜索树
 * </desc>
 */
public class BST<E extends Comparable<E>> {

    /**
     * 根节点
     */
    private Node root;
    /**
     * 节点个数
     */
    private int size;

    public BST() {
        size = 0;
        root = null;
    }


    /**
     * 添加一个节点
     *
     * @param e 节点值
     */
    public void add(E e) {
        root = add(e, root);
    }


    public int getSize() {
        return size;
    }


    public void preOrder() {
        preOrder(root);
    }

    public void postOrder() {
        postOrder(root);
    }


    public void inOrder() {
        inOrder(root);
    }

    /**
     * 前序遍历
     */
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);

    }

    /**
     * 后序遍历
     */
    public void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 中序遍历
     */
    public void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }


    private Node add(E e, Node node) {
        if (node == null) {
            size++;
            return new Node(e);
        }

        final int cmpRes = e.compareTo(node.e);
        if (cmpRes > 0) {
            node.right = add(e, node.right);
        } else if (cmpRes < 0) {
            node.left = add(e, node.left);
        }
        return node;
    }


    private class Node {
        private E e;
        private Node left;
        private Node right;

        Node() {
            this(null);
        }

        Node(E e) {
            this.e = e;
        }
    }

}
